﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace CTSexercises
{
    public class TreeNode<T> where T : IComparable<T>
    {
        private T data;
        private TreeNode<T> left;
        private TreeNode<T> right;

        public T Data
        {
            get
            {
                return data;
            }
            set
            {
                data = value;
            }
        }

        public TreeNode<T> Left
        {
            get
            {
                return left;
            }
            set
            {
                left = value;
            }
        }

        public TreeNode<T> Right
        {
            get
            {
                return right;
            }
            set
            {
                right = value;
            }
        }
    }

    public struct BinarySearchTree<T>
        where T: IComparable<T>
    {
        private TreeNode<T> root;

        public void AddElement(T data)
        {
            if (data != null)
            {
                AddElement(data, root);
            }
            else
            {
                throw new NullReferenceException("Data not initialized.");
            }
        }

        private void AddElement(T data, TreeNode<T> startRoot)
        {
            if (startRoot == null)
            {
                startRoot = new TreeNode<T>();
                startRoot.Data = data;
                startRoot.Left = null;
                startRoot.Right = null;
            }
            else if (data.CompareTo(startRoot.Data) < 0)
            {
                AddElement(data, startRoot.Left);
            }
            else
            {
                AddElement(data, startRoot.Right);
            }

        }

        public bool Contains(T data)
        {
             return Contains(data, root);
        }

        private bool Contains(T data, TreeNode<T> startRoot)
        {
            if (startRoot == null)
            {
                return false;
            }
            else if (startRoot.Data.CompareTo(data) == 0)
            {
                return true;
            }
            else if (data.CompareTo(startRoot.Data) < 0)
            {
                return Contains(data, startRoot.Left);
            }
            else
            {
                return Contains(data, startRoot.Right);
            }
        }
    }
}
